package nowcoder.offer;

/**
 * 二叉树的下一个结点
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-29 14:03
 */
public class GetNext {

    public TreeLinkNode solution(TreeLinkNode pNode){
        if (pNode.right != null){
            TreeLinkNode node = pNode.right;
            while (node.left != null){
                node = node.left;
            }
            return node;
        }else{
            TreeLinkNode node = pNode.next;
            if (node == null) return null;
            if (node.left == pNode)
                return node;
            TreeLinkNode grand = node.next;
            if (grand==null||grand.right == node) return null;
            while (node.next != null)
                node = node.next;
            return node;
        }
    }

}


class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

